package com.mlamp.寻找丑数;

public class 寻找丑数算法 {

    public static void main(String[] args) {
        寻找丑数算法 instance = new 寻找丑数算法();
        instance.findUglyNumber(2);
        System.out.println(findUglyNumber3(2));
    }

    /**
     * 动态规划寻找丑数
     *
     * @param number
     */

    public static int findUglyNumber3(int number) {
        int[] res = new int[1690];
        res[0] = 1;
        int ugly, i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < 1690; i++) {
            ugly = Math.min(Math.min(res[i2] * 2, res[i3] * 3), res[i5] * 5);
            res[i] = ugly;
            if (ugly == res[i2] * 2) ++i2;
            if (ugly == res[i3] * 3) ++i3;
            if (ugly == res[i5] * 5) ++i5;
        }
        return res[number - 1];
    }


    public void findUglyNumber(int number) {
        int index = 0;
        int start = 1;
        while (index < number) {
            if (isUgly(start++)) {
                index++;
            }
        }
        System.out.println(String.format("第 %s 个 丑数是 %s", number, start - 1));
        return;
    }


    int compare(int number1, int number2, int number3) {
        return Math.min(number1, Math.min(number2, number3));
    }


    public int findUglyNumber2(int N) {
        int[] uglyNumber = new int[99999];
        uglyNumber[0] = 1;
        int count = 1;
        while (true) {
            int number2 = 0, number3 = 0, number5 = 0;
            for (int index = 0; index < count; index++) {
                if (uglyNumber[index] * 2 > uglyNumber[count - 1]) {
                    number2 = uglyNumber[index] * 2;
                    break;
                }
            }
            for (int index = 0; index < count; index++) {
                if (uglyNumber[index] * 3 > uglyNumber[count - 1]) {
                    number3 = uglyNumber[index] * 3;
                    break;
                }
            }
            for (int index = 0; index < count; index++) {
                if (uglyNumber[index] * 5 > uglyNumber[count - 1]) {
                    number5 = uglyNumber[index] * 5;
                    break;
                }
            }
            uglyNumber[count++] = compare(number2, number3, number5);
            if (count == N) return uglyNumber[count - 1];
        }
    }


    public boolean isUgly(int number) {
        while (number % 2 == 0) {
            number = number / 2;
        }

        while (number % 3 == 0) {
            number = number / 3;
        }

        while (number % 5 == 0) {
            number = number / 5;
        }
        if (number == 1) return true;
        else return false;
    }
}
